#include <atomic>
#include <memory>
#include <thread>

template<typename T>
class MPMCLockFreeQueue {
private:
    // 节点结构定义
    struct Node;
    
    // 带有外部计数的节点指针
    struct CountedNodePtr {
        int external_count;  // 外部计数器，用于管理指针的引用计数
        Node* ptr;          // 指向实际节点的指针
    };

    // 队列节点结构
    struct Node {
        std::shared_ptr<T> data;       // 存储的数据
        std::atomic<int> internal_count; // 内部计数器，用于管理节点的引用计数
        CountedNodePtr next;            // 下一个节点指针（带外部计数）

        Node() : internal_count(0), next({0, nullptr}) {}
        
        // 释放节点引用
        void release_ref() {
            // 减少内部计数，如果计数归零则删除节点
            int old_count = internal_count.fetch_sub(1);
            if (old_count == 1) {
                delete this;
            }
        }
    };

    // 队列头指针（带外部计数）
    std::atomic<CountedNodePtr> head;
    // 队列尾指针（带外部计数）
    std::atomic<CountedNodePtr> tail;

    // 增加外部引用计数（线程安全）
    static void increase_external_count(std::atomic<CountedNodePtr>& counter,
                                      CountedNodePtr& old_counter) {
        CountedNodePtr new_counter;
        do {
            new_counter = old_counter;
            ++new_counter.external_count;  // 增加外部计数
        } while (!counter.compare_exchange_strong(old_counter, new_counter));  // CAS操作确保原子性
        old_counter.external_count = new_counter.external_count;
    }

    // 释放外部计数器
    static void free_external_counter(CountedNodePtr& old_node_ptr) {
        Node* const ptr = old_node_ptr.ptr;
        // 计算需要减少的内部计数值
        int const count_increase = old_node_ptr.external_count - 2;   <-----------
        
        // 增加内部计数（可能为负值）
        int old_count = ptr->internal_count.fetch_add(count_increase);
        if (old_count == -count_increase) {  // 如果内部计数归零
            delete ptr;  // 删除节点
        }
    }

    // 设置新的尾节点（线程安全）
    void set_new_tail(CountedNodePtr& old_tail, CountedNodePtr const& new_tail) {
        Node* const current_tail_ptr = old_tail.ptr;
        // 使用CAS更新尾指针
        while (!tail.compare_exchange_weak(old_tail, new_tail)) {
            if (old_tail.ptr == current_tail_ptr)  // 如果尾节点未改变
                break;
        }
        if (old_tail.ptr == current_tail_ptr) {  // 成功更新
            free_external_counter(old_tail);  // 释放旧尾节点的外部计数
        } else {  // 其他线程已经更新了尾节点
            current_tail_ptr->release_ref();  // 减少当前节点的引用计数
        }
    }

public:
    // 构造函数 - 初始化一个空队列（带哑节点）
    MPMCLockFreeQueue() {
        CountedNodePtr dummy;
        dummy.ptr = new Node();  // 创建哑节点
        dummy.external_count = 1; // 初始外部计数为1
        head.store(dummy);       // 头指针指向哑节点
        tail.store(dummy);      // 尾指针指向哑节点
    }

    // 禁止拷贝构造
    MPMCLockFreeQueue(const MPMCLockFreeQueue&) = delete;
    // 禁止赋值操作
    MPMCLockFreeQueue& operator=(const MPMCLockFreeQueue&) = delete;

    // 析构函数 - 清空队列
    ~MPMCLockFreeQueue() {
        while (pop());  // 弹出所有剩余元素
        delete head.load().ptr;  // 删除最后的哑节点
    }

    // 入队操作（线程安全）
    void push(T new_value) {
        // 准备新数据
        std::shared_ptr<T> new_data(std::make_shared<T>(std::move(new_value)));
        
        // 准备新节点
        CountedNodePtr new_next;
        new_next.ptr = new Node();
        new_next.external_count = 1;
        
        CountedNodePtr old_tail = tail.load();
        
        for (;;) {  // 循环直到成功插入
            // 增加尾节点的外部引用计数
            increase_external_count(tail, old_tail);
            
            Node* const old_tail_ptr = old_tail.ptr;
            T* old_data = nullptr;
            
            // 尝试将数据存入尾节点
            if (old_tail_ptr->data.compare_exchange_strong(old_data, new_data.get())) {
                // 设置新节点的next指针
                old_tail_ptr->next = new_next;
                // 更新尾指针
                old_tail = tail.exchange(new_next);
                // 释放旧尾节点的外部计数
                free_external_counter(old_tail);
                // 释放数据所有权
                new_data.release();
                break;
            }
            
            // CAS失败，释放当前尾节点的引用
            old_tail_ptr->release_ref();
            // 重新加载尾指针
            old_tail = tail.load();
        }
    }

    // 出队操作（线程安全）
    std::shared_ptr<T> pop() {
        CountedNodePtr old_head = head.load();
        for (;;) {  // 循环直到成功弹出
            // 增加头节点的外部引用计数
            increase_external_count(head, old_head);
            
            Node* const ptr = old_head.ptr;
            // 如果队列为空
            if (ptr == tail.load().ptr) {
                ptr->release_ref();  // 释放节点引用
                return std::shared_ptr<T>();  // 返回空指针
            }
            
            // 尝试移动头指针
            if (head.compare_exchange_strong(old_head, ptr->next)) {
                // 获取数据
                std::shared_ptr<T> res;
                res.swap(ptr->data);
                // 释放旧头节点的外部计数
                free_external_counter(old_head);
                return res;
            }
            
            // CAS失败，释放当前头节点的引用
            ptr->release_ref();
        }
    }
};